1759G - Restore the Permutation - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define el '\n'
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define vi vector<int>
#define vl vector<ll>
#define popcount __builtin_popcountll
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int mod = 1e9 + 7;
const ll INF = 1e17 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l , ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}



int main(){
    ios;
    int t;cin >> t;
    while(t--){
        int n;cin >> n;
        vector<int> arr(n / 2);
        for(auto &x:arr)cin >> x;
        vector<int> res(n + 1);
        map<int,int> mp;
        for(int i = 1;i <= n / 2;i++){
            mp[arr[i - 1]] = 2 * i;
            res[2 * i] = arr[i - 1];
        }
        set<int> s;
        bool ok = true;
        for(int i = n;i >= 1;i--){
            if(!mp[i]){
                if(s.empty()){
                    ok = false;
                    break;
                }else{
                    const int idx = *s.rbegin();
                    res[idx - 1] = i;
                    s.erase(idx); 
                }
            }else{
                s.insert(mp[i]);
            }
        }
        if(!ok){
            cout << -1 << el;
        }else{
            for(int i = 1;i <= n;i++){
                cout << res[i] << " ";
            }
            cout << el;
        }
    }
}